// 1.排序后直接取
// 时间复杂度：O(n log n)（取决于排序算法）
// 空间复杂度：O(1)（原地排序）
function findKth(arr, k) {
  const arrSort = arr.sort((a, b) => b - a)
  return (arrSort[k - 1])
}


// 2.快速选择算法（最优解）
// 用快速排序的思想，排序后选择数组第K大的元素
// 只递归处理包含目标的那一部分,时间复杂度为 O(n)
function findKthLargest(nums, k) {
  // l - 当前处理区间的左边界;r - 当前处理区间的右边界; k - 目标元素在排序后的数组中的索引
  const quickselect = (l, r, k) => {
    // 递归终止条件：区间仅一个元素时返回
    if (l === r) return nums[k];

    // 选择最左元素为基准值
    const partition = nums[l];
    let i = l - 1, j = r + 1;

    // 分区操作：将数组分为 <=partition 和 >=partition 两部分
    while (i < j) {
      i++; while (nums[i] < partition) i++;  // 找左半部分第一个 >=partition 的元素
      j--; while (nums[j] > partition) j--;  // 找右半部分第一个 <=partition 的元素
      if (i < j) [nums[i], nums[j]] = [nums[j], nums[i]];  // 交换不满足条件的元素
    }

    // 递归处理包含目标的子区间
    if (k <= j) return quickselect(l, j, k);  // 目标在左半区间
    else return quickselect(j + 1, r, k);     // 目标在右半区间
  };

  // 第 k 大的元素，在排序后的数组中它位于 n-k 的位置（0-based 索引）
  return quickselect(0, nums.length - 1, nums.length - k);
}



// 示例测试
const nums = [3, 2, 1, 5, 6, 4];
const k = 2;
console.log(findKthLargest(nums, k)); // 输出: 5